package 数组;

/**
 * Author: Zhang Dongwei
 * Date: 2022/3/31 20:38
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，
 * 如果目标值存在返回下标，否则返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 二分查找_704 {
    public static void main(String[] args) {
        int[] nums = new int[] {-78, -12, -2, 0, 1, 2, 3, 45, 78, 98, 124, 234, 478, 547, 784, 1234, 4587};
        int target = 234;
        Solution solution = new 二分查找_704().new Solution();
        int res = solution.search(nums, target);
        System.out.println(res);
    }

    class Solution {
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int mid = 0;
            while (left <= right){
                mid = (left + right) / 2;
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] < target){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
            return -1;
        }
    }

    // 自己写的，有问题，超时了
    class Solution1 {
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length-1;
            int mid = (left + right)/2;
            while (nums[mid] != target){
                mid = (left + right)/2;
                if(nums[mid] < target){
                    left = mid + 1;
                    continue;
                }else if(nums[mid] > target){
                    right = mid -1;
                    continue;
                }
                return mid;
            }
            return -1;
        }
    }

    // 官方答案
    class Solution2 {
        public int search(int[] nums, int target) {
            int low = 0, high = nums.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;  // mid = (high + low) / 2; 这样防止high+low越界
                int num = nums[mid];
                if (num == target) {
                    return mid;
                } else if (num > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }
    }
}
